题面

解题思路

树链剖分+差分

分析

这道题的基本思路和 $\mathtt{Link}$ 相同，考虑如何维护 $k$ 次方，仍然按照同样的思路，既然是累加的和，那么我们就可以把这些数的 $k$ 次方差分，累加即可得到结果

warning

注意差分顺序

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define p 998244353
#define N 50003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct node{
    int i,val;
    node(int a,int b):i(a),val(b){}
    node(){}
}cur;
int head[N],ver[N<<1],nxt[N<<1],n,m,t,k,L,R,Ans[N];
int seg[N],top[N],rev[N],Ie[N],f[N<<2],num,sum[N<<2];
int dep[N],son[N],size[N],fa[N],tag[N<<2],ans,pos;
queue<node>P[N];
inline int Pw(rll a) {
    rint b=k;rll res=1;
    for(;b;b>>=1,a=a*a%p)
        if(b&1) res=res*a%p;
    return res;
}
inline int dec(rint x){return(x>=p)?x-p:x;}
inline int rec(rint x){return(x<0)?x+p:x;}
inline void add(rint x,rint y) {
    ver[++t]=y,nxt[t]=head[x],head[x]=t,
    ver[++t]=x,nxt[t]=head[y],head[y]=t;
}
inline void dfs1(rint k) {
    rint i,to;
    dep[k]=dep[fa[k]]+1,size[k]=1;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];if(to==fa[k]) continue;
        fa[to]=k,dfs1(to),size[k]+=size[to];
        if(size[to]>size[son[k]])
            son[k]=to;
    }
}
inline void dfs2(rint k) {
    if(son[k]) {
        seg[son[k]]=++num,
        top[son[k]]=top[k],
        rev[num]=son[k],
        dfs2(son[k]);
    }
    rint i,to;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];if(top[to]) continue;
        seg[to]=++num,
        top[to]=rev[num]=to,dfs2(to);
    }
}
inline void built(rint k,rint l,rint r) {
    if(l==r){sum[k]=Ie[dep[rev[l]]];return;}
    rint m=(l+r)>>1,ls=k<<1;
    built(ls,l,m),built(ls|1,m+1,r),
    sum[k]=dec(sum[ls]+sum[ls|1]);
}
inline void push(rint k,rint l,rint r) {
    f[k]=dec(f[k]+(LL)tag[k]*sum[k]%p);
    if(l!=r) {
        rint ls=k<<1;
        tag[ls]+=tag[k],tag[ls|1]+=tag[k];
    }tag[k]=0;
}
inline void Modify(rint k,rint l,rint r) {
    if(tag[k]) push(k,l,r);
    if(r<L||R<l) return;
    if(L<=l&&r<=R){tag[k]=1;return push(k,l,r);}
    rint m=(l+r)>>1,ls=k<<1;
    Modify(ls,l,m),Modify(ls|1,m+1,r),
    f[k]=dec(f[ls]+f[ls|1]);
}
inline void Query(rint k,rint l,rint r) {
    if(tag[k]) push(k,l,r);
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {ans=dec(ans+f[k]);return;}
    rint m=(l+r)>>1,ls=k<<1;
    Query(ls,l,m),Query(ls|1,m+1,r);
}
#define fx top[x]
inline void Add(rint x) {
    while(fx!=1) {
        L=seg[fx],R=seg[x],
        Modify(1,1,n),x=fa[fx];
    }
    L=1,R=seg[x],Modify(1,1,n);
}
inline int Ask(rint x) {
    ans=0;
    while(fx!=1) {
        L=seg[fx],R=seg[x],
        Query(1,1,n),x=fa[fx];
    }
    L=1,R=seg[x],Query(1,1,n);
    return ans;
}
int main()
{
    rint i,j;
    n=read(),m=read(),k=read();
    for(i=n;i;i--) Ie[i]=Pw(i),Ie[i+1]=rec(Ie[i+1]-Ie[i]);//差分是i^k-(i-1)^k的值
    for(i=2;i<=n;i++) add(read(),i);
    for(i=1;i<=m;i++)
        pos=read(),P[pos].push(node(i,read()));
    num=seg[1]=rev[1]=top[1]=1,
    dfs1(1),dfs2(1),built(1,1,n);
    for(i=1;i<=n;i++) {
        Add(i);
        while(!P[i].empty()) {
            cur=P[i].front(),P[i].pop(),
            Ans[cur.i]=Ask(cur.val);
        }
    }
    for(i=1;i<=m;i++) printf("%d\n",Ans[i]);
    return 0;
}

devil.